
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1685. -- [Usaco2005 Oct]Allowance -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1685: [Usaco2005 Oct]Allowance</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>55&nbsp;&nbsp;<span class=green>Solved: </span>44<br>[<a href='submitpage.php?id=1685'>Submit</a>][<a href='problemstatus.php?id=1685'>Status</a>][<a href='bbs.php?id=1685'>Discuss</a>]</center><h2>Description</h2><div class=content>As a reward for record milk production, Farmer John has decided to
start paying Bessie the cow a small weekly allowance. FJ has a set
of coins in N (1 <= N <= 20) different denominations, where each
denomination of coin evenly divides the next-larger denomination
(e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins).
Using the given set of coins, he would like to pay Bessie at least
some given amount of money C (1 <= C <= 100,000,000) every week.
Please help him compute the maximum number of weeks he can pay
Bessie.

</div><h2>Input</h2><div class=content>* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Each line corresponds to a denomination of coin and
        contains two integers: the value V (1 <= V <= 100,000,000) of
        the denomination, and the number of coins B (1 <= B <=
        1,000,000) of this denomation in Farmer John's possession.

约翰要对Bessie发每周津贴。约翰有n(1<=n<=20)种币值的硬币，面值小的硬币总能整除面值较大的硬币。（比如币值有如下几种：1美分，5美分，10美分，50美分......），每种硬币的面值V<=100,000,000，个数B<=1,000,000，利用给定的这些硬币，他将要每周付给Bessie一定金额的钱c(1<=c<=100,000,000)，注意付的钱可以超过c。
</div><h2>Output</h2><div class=content>* Line 1: A single integer that is the number of weeks Farmer John can
        pay Bessie at least C allowance

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3 6<br />
10 1<br />
1 100<br />
5 120<br />
<br />
INPUT DETAILS:<br />
<br />
FJ would like to pay Bessie 6 cents per week.  He has 100 1-cent coins,<br />
120 5-cent coins, and 1 10-cent coin.<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>111<br />
<br />
OUTPUT DETAILS:<br />
<br />
FJ can overpay Bessie with the one 10-cent coin for 1 week, then pay Bessie<br />
two 5-cent coins for 10 weeks and then pay Bessie one 1-cent coin and one<br />
5-cent coin for 100 weeks.</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1685'>Submit</a>][<a href='problemstatus.php?id=1685'>Status</a>][<a href='bbs.php?id=1685'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
